<?php
/**
 * @title 130. 被围绕的区域 - 迭代
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class Solution {

    /**
     * @param String[][] $board
     * @return NULL
     */
    function solve(&$board) {
        /**
         * @since 2020-08-11 矩阵高,宽
         */
        $h = count($board);
        $w = count($board[0]);

        /**
         * @since 2020-08-11 初始化一个返回矩阵
         */
        $result = array_fill(0, $h, array_fill(0, $w, "X"));
        // return $result;

        /**
         * @since 2020-08-11 先扫4条边
         * @since 2020-08-11 上下2条边
         */
        $nexts = [];
        for($i=0; $i<=$w-1; $i++){
            if($board[0][$i] == "O"){
                $result[0][$i] = "O";
                $nexts[] = [0, $i];
            } else {}

            if($board[$h-1][$i] == "O"){
                $result[$h-1][$i] = "O";
                $nexts[] = [$h-1, $i];
            } else {}
        }

        /**
         * @since 2020-08-11 左右2条边
         */
        for ($i=1; $i<=$h-2; $i++){
            if($board[$i][0] == "O"){
                $result[$i][0] = "O";
                $nexts[] = [$i, 0];
            } else {}

            if($board[$i][$w-1] == "O"){
                $result[$i][$w-1] = "O";
                $nexts[] = [$i, $w-1];
            } else {}
        }

        /**
         * @since 2020-08-11 递归, 四个方向查找
         */
        while($nexts){
            $nextTmp = [];

            foreach ($nexts as list($n, $m)){
                /**
                 * @since 2020-08-11 4个方向查找
                 * @since 2020-08-11 向上
                 */
                if($n>0){
                    if($board[$n-1][$m] == "O" AND $result[$n-1][$m] != "O"){
                        $result[$n-1][$m] = "O";
                        $nextTmp[] = [$n-1, $m];
                    } else {}
                } else {}

                /**
                 * @since 2020-08-11 向下
                 */
                if($n<$h-1){
                    if($board[$n+1][$m] == "O" AND $result[$n+1][$m] != "O"){
                        $result[$n+1][$m] = "O";
                        $nextTmp[] = [$n+1, $m];
                    } else {}
                } else {}

                /**
                 * @since 2020-08-11 向左
                 */
                if($m>0){
                    if($board[$n][$m-1] == "O" AND $result[$n][$m-1] != "O"){
                        $result[$n][$m-1] = "O";
                        $nextTmp[] = [$n, $m-1];
                    } else {}
                } else {}

                /**
                 * @since 2020-08-11 向右
                 */
                if($m<$w-1){
                    if($board[$n][$m+1] == "O" AND $result[$n][$m+1] != "O"){
                        $result[$n][$m+1] = "O";
                        $nextTmp[] = [$n, $m+1];
                    } else {}
                } else {}
            }

            /**
             * @since 2020-08-11 下次循环
             */
            $nexts = $nextTmp;
        }

        /**
         * @return
         */
        $board = $result;
        return $result;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.11.php
 */
$datas = [
    // [
    //     ['X'],
    // ],
    // [
    //     ['X'],
    //     ['X'],
    //     ['X'],
    // ],
    [
        ['X', 'X', 'X', 'X'],
        ['X', 'O', 'O', 'X'],
        ['X', 'X', 'O', 'X'],
        ['X', 'O', 'X', 'X'],
    ],
    // [
    //     ['X', 'X', 'X', 'X', 'X'],
    //     ['X', 'O', 'O', 'X', 'X'],
    //     ['X', 'X', 'O', 'X', 'X'],
    //     ['X', 'O', 'X', 'X', 'X'],
    // ],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    foreach ($data as $r){
        echo "[", implode(",", $r) ,"], <br>";
    }
    echo str_repeat("<br>", 3);

    $obj = new Solution();
    $result = $obj->solve($data);
    // var_dump($result);

    foreach ($result as $r){
        echo "[", implode(",", $r) ,"], <br>";
    }

    echo str_repeat("<br>", 3);
}
$xhprof->end();
